import java.security.Key;
import java.util.ArrayList;
import java.util.List;

public class test_24_09_09 {

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        class Solution01 {
            public ListNode mergeNodes(ListNode head) {
                ListNode dummy = new ListNode(0);
                ListNode node = head.next;
                ListNode newhead = dummy;
                while (node != null) {
                    int sum = 0;
                    while (node.val != 0) {
                        sum += node.val;
                        node = node.next;
                    }
                    node = node.next;
                    newhead.next = new ListNode(sum);
                    newhead = newhead.next;
                }
                return dummy.next;
            }
        }

        class Pair {
            public int key;
            public String val;

            public Pair(int key, String val) {
                this.val = val;
                this.key = key;
            }
        }


        /* 链式地址哈希表 */
        class HashMapChaining {
            int size; // 键值对数量
            int capacity; // 哈希表容量
            double loadThres; // 触发扩容的负载因子阈值
            int extendRatio; // 扩容倍数
            List<List<Pair>> buckets; // 桶数组

            /* 构造方法 */
            public HashMapChaining() {
                size = 0;
                capacity = 4;
                loadThres = 2.0 / 3.0;
                extendRatio = 2;
                buckets = new ArrayList<>(capacity);
                for (int i = 0; i < capacity; i++) {
                    buckets.add(new ArrayList<>());
                }
            }

            /* 哈希函数 */
            int hashFunc(int key) {
                return key % capacity;
            }

            /* 负载因子 */
            double loadFactor() {
                return (double) size / capacity;
            }

            /* 查询操作 */
            String get(int key) {
                int index = hashFunc(key);
                List<Pair> bucket = buckets.get(index);
                // 遍历桶，若找到 key ，则返回对应 val
                for (Pair pair : bucket) {
                    if (pair.key == key) {
                        return pair.val;
                    }
                }
                // 若未找到 key ，则返回 null
                return null;
            }

            /* 添加操作 */
            void put(int key, String val) {
                // 当负载因子超过阈值时，执行扩容
                if (loadFactor() > loadThres) {
                    extend();
                }
                int index = hashFunc(key);
                List<Pair> bucket = buckets.get(index);
                // 遍历桶，若遇到指定 key ，则更新对应 val 并返回
                for (Pair pair : bucket) {
                    if (pair.key == key) {
                        pair.val = val;
                        return;
                    }
                }
                // 若无该 key ，则将键值对添加至尾部
                Pair pair = new Pair(key, val);
                bucket.add(pair);
                size++;
            }

            /* 删除操作 */
            void remove(int key) {
                int index = hashFunc(key);
                List<Pair> bucket = buckets.get(index);
                // 遍历桶，从中删除键值对
                for (Pair pair : bucket) {
                    if (pair.key == key) {
                        bucket.remove(pair);
                        size--;
                        break;
                    }
                }
            }

            /* 扩容哈希表 */
            void extend() {
                // 暂存原哈希表
                List<List<Pair>> bucketsTmp = buckets;
                // 初始化扩容后的新哈希表
                capacity *= extendRatio;
                buckets = new ArrayList<>(capacity);
                for (int i = 0; i < capacity; i++) {
                    buckets.add(new ArrayList<>());
                }
                size = 0;
                // 将键值对从原哈希表搬运至新哈希表
                for (List<Pair> bucket : bucketsTmp) {
                    for (Pair pair : bucket) {
                        put(pair.key, pair.val);
                    }
                }
            }

            /* 打印哈希表 */
            void print() {
                for (List<Pair> bucket : buckets) {
                    List<String> res = new ArrayList<>();
                    for (Pair pair : bucket) {
                        res.add(pair.key + " -> " + pair.val);
                    }
                    System.out.println(res);
                }
            }
        }

    }
}
